#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
const int N=1e6+10;
int flg[N];
int val[N],nex[N];
int main()
{
	int n;
	int st;
	cin>>st>>n;
	for(int i=1;i<=n;i++)
	{
		int idx;
		cin>>idx;
		cin>>val[idx]>>nex[idx];
	}
	vector<int> del;
	vector<int> prov;
	for(int i=st;i!=-1;i=nex[i])
	{
		if(flg[abs(val[i])])
		{
			del.push_back(i);
		}	
		else{
			prov.push_back(i);
			flg[abs(val[i])]=1;
		}
	}
	
	for(int i=0;i<prov.size();i++)
	{
		if(i+1<prov.size())
			printf("%05d %d %05d\n",prov[i],val[prov[i]],prov[i+1]);
		else
			printf("%05d %d %d\n",prov[i],val[prov[i]],-1);
	}
	for(int i=0;i<del.size();i++)
	{
		if(i+1<del.size())
			printf("%05d %d %05d\n",del[i],val[del[i]],del[i+1]);
		else
			printf("%05d %d %d\n",del[i],val[del[i]],-1);
	}
	return 0;
}
